package com.ctrip.study.algorithm.pratice;

import java.util.Arrays;

import java_cup.runtime.lr_parser;

import org.junit.Test;

import com.mysql.fabric.xmlrpc.base.Array;

import junit.framework.TestCase;

/**
 * Given an array and a value, r
 * emove all instances of that value in place and return the new length.
 * The order of elements can be changed. 
 * It doesn't matter what you leave beyond the new length
 */
public class RemoveElement extends TestCase{
	
	@Test
	public void test(){
		assertEquals(2, removeElement(new int[]{30,30}, 29));
		assertEquals(1, removeElement(new int[]{29,30}, 29));
		assertEquals(1, removeElement(new int[]{30,29}, 29));
		assertEquals(0, removeElement(new int[]{29,29}, 29));
		assertEquals(2, removeElement(new int[]{29,30,29,30}, 29));
	}

	public int removeElement(int[] array, int elem) {
		if(array.length == 1){
			return array[0] == elem ? 0 : 1;
		}
		int low = 0;
		int high = array.length - 1;
		while(low <= high){
			if(array[low] == elem){
				while(high > low && array[high] == elem){
					high--;
					if(high == 0){
						return 0;
					}
				}
				swap(array, low, high);
			}
			if(low == high && (low + 1) == array.length && array[low] != elem){
				return low + 1;
			}else if (low != high){
				low++;
			}else{
				break;
			}
		}
		return low;
    }
	
	public void swap(int[] array, int a, int b){
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}
	
}
